package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
 * (C卷,200分)- 数组二叉树（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2*N和2*N+1，并且我们用值-1代表一个节点为空。
 * <p>
 * 给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。
 * <p>
 * 输入描述
 * <p>
 * 输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
 * <p>
 * 注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
 * <p>
 * 输入的树最多为7层。
 * <p>
 * 输出描述
 * <p>
 * 输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。
 * <p>
 * 用例
 * <p>
 * 输入	3 5 7 -1 -1 2 4
 * <p>
 * 输出	3 7 2
 * <p>
 * 说明	最小叶子节点的路径为3 7 2。
 * <p>
 * 输入	5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
 * <p>
 * 输出	5 8 7 6
 * <p>
 * 说明	最小叶子节点的路径为5 8 7 6，注意数组仅存储至最后一个非空节点，故不包含节点“7”右子节点的-1。
 */
public class ArrayBinaryTree {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        Integer[] arr =
                Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);*/

        String input = "5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6";
        Integer[] arr = Arrays.stream(input.split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        System.out.println(getResult(arr));
    }

    public static String getResult(Integer[] arr) {
        int n = arr.length - 1;

        // 最小叶子节点的值
        int min = Integer.MAX_VALUE;
        // 最小叶子节点的索引
        int minIdx = -1;

        // 求解最小叶子节点的值和索引
        for (int i = n; i >= 1; i--) {
            if (arr[i] != -1) {
                if (i * 2 + 1 <= n && arr[i * 2 + 1] != -1) {
                    continue;
                }
                if (i * 2 + 2 <= n && arr[i * 2 + 2] != -1) {
                    continue;
                }
                if (min > arr[i]) {
                    min = arr[i];
                    minIdx = i;
                }
            }
        }

        // path用于缓存最小叶子节点到根的路径
        LinkedList<Integer> path = new LinkedList<>();
        path.addFirst(min);

        // 从最小叶子节点开始向上找父节点，直到树顶
        while (minIdx != 0) {
            int f = (minIdx - 1) / 2;
            path.addFirst(arr[f]);
            minIdx = f;
        }

        return path.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }
}